Curve extraction is a process of identifying geometric curves in sensor data. Sensor data is understood to mean herein an amount of information which is derived from an object and which is regularly arranged according to two coordinates. The information may have been derived by means of optical means or other means, such as a scanning electron microscope or radio-telescope. A geometric curve is a curve which has an associated equation, such as a line, circle, or an ellipse. Extracting or identifying geometric curves is a particularly useful task in the field of model-based vision. Practical applications of the process of finding curves in data are numerous. For example, a robot can be guided by identifying curves representing objects within an associated camera's field of view. An image scanned by the camera may be processed by a computer to locate curves such as the outline of a fluorescent light on the ceiling along a desired path of the robot's travel. The robot may then re-orient itself according to the reference co-ordinates of the edge data representing the fluorescent light or other located curve.
A scanned image may include two dimensional (2D) curves, such as lines, circles, parabolas and ellipses in the form of sensor data. Sensor data generally consists of points on a 2D array. These points are most often stored in the form of binary data however other coding schemes yielding decodable indicia may be used to represent the points. The binary data sometimes referred to as edge data is produced by processing an intensity image using edge detection, followed by thresholding to produce a binary edge map of edge points or edge data. Thresholding is a well known concept and is described in U.S. Pat. No. 4,644,583 in the name of Watanabe et al.
Many methods currently exist for finding curves within edge data. In general the primary factors affecting performance are: the duration of time required to match a curve with the relevant data, and, the space required to store data. In the past, the most widely used approach to extract or locate curves has been the Hough transform (HT) disclosed by D. Ballard and C. Brown, in a book entitled Computer Vision, published by Prentice Hall, 1992. Ballard discloses the basic principle of operation. Each edge point votes for all parameter combinations that could have produced it. This voting process requires that the parameter space be partitioned into cells (usually rectangular) by quantizing each of the dimensions of this space; then each edge point adds a single vote to all the cells whose combination of parameters could have produced a geometric curve through that point. An individual cell in a parameter space thus describes the edge points covered by all the geometric curves whose parameter vectors are contained in the cell. These points taken together define a template of the same approximate shape as the curve, whose size is determined by the cell size. When this template is applied to the data it returns the same set of points that voted for the cell in the standard HT algorithm. Thus, the HT is a space inefficient method of performing template matching. If there are N edge points, then for each of these points the voting process must mark the appropriate cell in the parameter space. Thus, the execution time for the HT s clearly proportional to N, the number of edge points in the array.
G. Roth and M. D. Levine disclose another method for finding curves in a paper entitled "A Genetic Algorithm for Primitive Extraction", published in the Proceedings of the Fourth International Conference on Genetic Algorithms, (San Diego), pp. 487-494, July 1991. However, as with many other methods, the most inefficient and computationally expensive method step is the step of matching a potential geometric curve against the sensor data. This matching process yields the number of points within a small template centered on the curve. This process is repeated a number of times, and the curve with the greatest number of points is located.
In a paper entitled, "A Ransac-Based Approach to Model Fitting And Its Application To Finding Cylinders In Range Data", published in Proceedings of the Seventh International Joint Conference on Artificial Intelligence, Volume II IJCAI 1981 24th-28th August, University of British Columbia Robert C. Bolles and Martin A. Fischler disclose another example of a method for finding curves. In particular, a method for finding ellipses in sensor data is disclosed. The method includes the steps of iteratively selecting sets of five points; computing the general second-order equation of the curve that passes through the points; and then determining whether or not the result is an ellipse that has approximately the right minor diameter and comes close to a sufficiently large number of the points. If these conditions are satisfied, the parameter values are used, and if not, another set of five points are used. The step of determining whether or not the result is an ellipse having a sufficiently large number of points is performed by evaluating residuals. Residuals are defined to be the errors of fit. In order to evaluate the residuals, the data in all the non-zero memory locations in the array are read. As a result, this time-consuming process of reading all the data in the array greatly increases the time required to locate a particular curve.
In the field of computer graphics, and more specifically, for the purpose of drawing curves on a computer display terminal, methods are known to perform the step of determining where all the points on a curve will be drawn on the screen or placed on an addressable array, given the equation of the curve and a points on the curve as a general input parameter. One such method commonly used for this drawing function is the "incremental method of curve generation". The general steps are as follows: a curve is generated from a point of origin up to a final point by the calculating of the elementary movement at each step which will determine the following point from the current point. At each step, the elementary movement can be calculated either using implicit methods, arithmetic methods, or structural properties. Incremental methods make use above all of integral arithmetic and generally avoid the use of multiplication and division operations.
Paul S. Heckbert in an article entitled Digital Line Drawing in a book entitled Graphics Gems, 1990, Academic Press, presents a practical implementation for Bresenham's algorithm (1965) for incremental curve generation of straight lines. Gerard Hegron in a book entitled Image Synthesis published by the MIT Press of Cambridge Massachusetts discloses several incremental curve generation algorithms, and more specifically Hegron discloses methods which generalizes Bresenham's algorithm to generate curves such as circles, parabolas and ellipses by incremental methods.
It has been found however, on such devices as display terminals and laser printers, that standard thin lines generated by incremental curve generation algorithms, have in some cases, been found to be too thin and not desirable. One solution to this problem in the graphics and computer arts is disclosed by Bob Wallis in an article entitled "Rendering Fat Lines on a Raster Grid" in a book entitled Graphics Gems, edited by Andrew S. Glassner and published by Academic Press 1990. Wallis discloses a method for rendering multi-pixel wide lines on a raster grid which overcomes the limitation of Bresenham's method and other incremental methods. In combination, the incremental curve generation method and the method disclosed by Wallis for rendering fat lines provide the steps required to draw a curve of width w given an equation for the curve and points on the curve. Although these methods appear to work satisfactorily for their intended purpose, to date, they have been generally limited in the application to providing expedient ways of drawings curves and not for the purpose of locating curves in sensor data.